To improve data transmission over a network, data is often compressed using data redundancy elimination (DRE) schemes. DRE schemes typically divide data blocks into chunks and replace redundant chunks with short identifiers, typically referred to as chunk signatures. Compression is achieved by sending signatures instead of raw data over the network. Two existing approaches for dividing data blocks are fixed-size division and pseudo-random division. Fixed-size division divides data blocks into pre-defined, fixed-sized chunks. Pseudo-random division selects chunk breakpoints based on the values of the bytes in the data block. Both of these approaches are typically characterized, by the expected chunk size. In any approach to chunking, the maximum compression ratio that can be achieved is estimated as a ratio of chunk signature size to the (expected) chunk length. Longer chunks typically provide better compression, since more raw data can be replaced with a smaller signature. However, longer chunks are less suitable for detecting small-sized redundancies within a data stream, because the size of detectable redundant pattern typically needs to be greater than the expected chunk size. Accordingly, in practice, increasing chunk size often results in poor compression ratios.